Dynamic Network Flows - Chapter 5: Instantaneous Dynamic Equilibria

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\sMid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\deriv}[2][]{\partial_{#1} #2} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\cexittime}[1][e]{A_{#1}} \newcommand{\network}{N} \newcommand{\tauPmin}{\tau_{p_{\min}}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \)

Shortest remaining instantaneous distance:
\[\bar R_v(\theta) \coloneqq \inf\Set{\sum_{e \in p}\Big(\tau_e + \tfrac{\ql(\theta)}{\nu_e}\Big) \SMid p \text{ a } v,t\text{-path}}\] $e = vw \in E$ active at time $\theta$ if \[\bar R_v(\theta) = \tau_e + \tfrac{\ql(\theta)}{\nu_e} + \bar R_w(\theta)\] Vickrey flow $f$ is instantaneous dynamic equilibrium (IDE) if \[f^+_e(\theta) \implies e \text{ active f.a. } e \in E \text{ and f.a.a. } \theta \in \IR\]

Fixed-Point Theorem: $X$ locally convex Hausdorff space, $K \subseteq X$ non-empty, convex, compact,
Fixed-Point Theorem: $\Gamma: K \to \PSet{K}$ with closed graph and $\Gamma(x)$ non-empty and convex for all $x \in K$
Fixed-Point Theorem:mmm $\implies \exists x \in K: x \in \Gamma(x)$

Lemma 4.4: For any $f^+_e: \IR \to \IRnn$ loc.-int. with $\supp(f^+_e) \subseteq \IRnn$ there exists a $f^-_e$ such that $(f^+_e,f^-_e)$ is a Vickrey flow.

Lemma 4.5: $(f^+_e,f^-_e)$ and $(g^+_e,g^-_e)$ two Vickrey flows with $f^+_e(\theta) = g^+_e(\theta)$ f.a.a. $\theta \leq T$. Then, $f^-_e(\theta) = g^-_e(\theta)$ f.a.a. $\theta \leq \cexittime(T)$.

Lemma 4.7: The (Vickrey-)edge loading mapping is sequentially weak-weak-continuous: \[\Phi_e^T: \set{f^+_e \in L^2(\IR) \sMid \supp(f^+_e) \subseteq [0,T], f^+_e \geq 0} \to L^1_{\mathrm{loc}}(\IR), f^+_e \mapsto f^-_e \text{ s.th. } (f^+_e,f^-_e) \text{ is Vickrey flow}\]

Theorem 5.5: For any $\network$ and network inflow rate $u$ such that

$u \in L^2(\IR)$ with bounded support,
$t$ is reachable from every node in $\network$ and
$\exists T \in \IRnn$ s.th. every IDE in $\network$ for $u$ terminates before $T$
all $\nu_e, \tau_e \in \INs$

there exists an IDE.

\[\begin{align} \sum_{e \in \edgesFrom{v}}x_e &= \sum_{e \in \edgesTo{v}}f^-_e(T) &&& \\ x_e &= 0 &&\text{ f.a. } e \notin \bar E(T) &(\ast)\\ x_e &\gt 0 \implies \psi_e(x_e)+a_w \leq \psi_{e'}(x_{e'})+a_{w'} &&\text{ f.a. } e=vw, e'=vw' \in \edgesFrom{v} & \end{align}\]

IDE-Extension Algorithm:

Input: $\network=$ with $\tau_e \gt 0$, $u$ right-constant, $f$ IDE until $T$ with r.-c. flow rates
Output: constant extension of $f$ to IDE until $T+\eps$ for some $\eps \gt 0$

(1) Fix topological order $v_n \prec \dots \prec v_1 = t$ wrt. $(V,\bar E(T))$

(2) Set $x_e \coloneqq 0$ f.a. $e \in \edgesFrom{t}$ and $a_t \coloneqq 0$

(3) For $i = 2, \dots, n$ Do

(4) .. Determine $(x_e) \in \IRnn^{\edgesFrom{v_i}}$ satisfying ($\ast$)

(5) .. Set $a_{v_i} \coloneqq \min\Set{\psi_e(x_e)+a_w \SMid e=v_iw \in \edgesFrom{v_i}\cap\bar E(T)}$

(6) Set $g^+_e(\theta) \coloneqq \begin{cases}f^+_e(\theta),&\text{ if }\theta \lt T\\x_e,&\text{ else}\end{cases}$ and $g^-_e \coloneqq \Phi_e(g^+_e)$ f.a. $e \in E$

(7) Choose $\eps \gt 0$ such that $g$ is IDE until $T+\eps$

(8) Return $(g^+_e,g^-_e)$ and $\eps$

Lemma: Let $v$ be a node with constant inflow and linear node labels at all nodes closer to the sink (during $[T,T+\alpha)$).
Lemma: Then only finitely many extensions are necessary at $v$.

$[T,T+\alpha) \to \IRnn, \theta \mapsto \tfrac{Q_{vw_i}(\theta)}{\nu_{vw_i}} + \bar R_{w_i}(\theta)$

Lemma 5.13: $\network$ with $\tau_e \gt 0$ and $t$ reachable from all $v \in V$, $u$ right-constant. Then, there exists $\alpha \gt 0$ s.th.
Lemma 5.13: For any right-constant IDE $f$ until $T$ and $\alpha' \leq \alpha$ with constant $u$ and $f^-_e$ during $[T,T+\alpha')$:
Lemma 5.13: We can extend $f$ to IDE until $T+\alpha'$ in finitely many phases.